/*-------------------------------------------------------------------------
 *
 * pg_list.h
 *	  interface for PostgreSQL generic list package
 *
 * Once upon a time, parts of Postgres were written in Lisp and used real
 * cons-cell lists for major data structures.  When that code was rewritten
 * in C, we initially had a faithful emulation of cons-cell lists, which
 * unsurprisingly was a performance bottleneck.  A couple of major rewrites
 * later, these data structures are actually simple expansible arrays;
 * but the "MyList" name and a lot of the notation survives.
 *
 * One important concession to the original implementation is that an empty
 * list is always represented by a null pointer (preferentially written NIL).
 * Non-empty lists have a header, which will not be relocated as long as the
 * list remains non-empty, and an expansible data array.
 *
 * We support four types of lists:
 *
 *	T_List: lists of pointers
 *		(in practice usually pointers to Nodes, but not always;
 *		declared as "void *" to minimize casting annoyances)
 *	T_IntList: lists of integers
 *	T_OidList: lists of Oids
 *	T_XidList: lists of TransactionIds
 *		(the XidList infrastructure is less complete than the other cases)
 *
 * (At the moment, ints, Oids, and XIDs are the same size, but they may not
 * always be so; be careful to use the appropriate list type for your data.)
 *
 *
 * Portions Copyright (c) 1996-2024, PostgreSQL Global Development Group
 * Portions Copyright (c) 1994, Regents of the University of California
 *
 * src/include/nodes/pg_list.h
 *
 *-------------------------------------------------------------------------
 */
#ifndef MY_PG_LIST_H
#define MY_PG_LIST_H

#include "nodes/nodes.h"


typedef union MyListCell
{
	void	   *ptr_value;
	int			int_value;
	Oid			oid_value;
	TransactionId xid_value;
} MyListCell;

typedef struct MyList
{
	NodeTag		type;			/* T_List, T_IntList, T_OidList, or T_XidList */
	int			length;			/* number of elements currently present */
	int			max_length;		/* allocated length of elements[] */
	MyListCell   *elements;		/* re-allocatable array of cells */
	/* We may allocate some cells along with the MyList header: */
	MyListCell	initial_elements[FLEXIBLE_ARRAY_MEMBER];
	/* If elements == initial_elements, it's not a separate allocation */
} MyList;


#define MYNIL                     ((MyList *) NULL)
/*
 * State structs for various looping macros below.
 */
typedef struct MyForEachState
{
	const MyList *l;				/* list we're looping through */
	int			i;				/* current element index */
} MyForEachState;


/*
 * These routines are small enough, and used often enough, to justify being
 * inline.
 */

/* Fetch address of list's first cell; NULL if empty list */
static inline MyListCell *
my_list_head(const MyList *l)
{
	return l ? &l->elements[0] : NULL;
}

/* Fetch address of list's last cell; NULL if empty list */
static inline MyListCell *
my_list_tail(const MyList *l)
{
	return l ? &l->elements[l->length - 1] : NULL;
}

/* Fetch list's length */
static inline int
my_list_length(const MyList *l)
{
	return l ? l->length : 0;
}

/*
 * Macros to access the data values within MyList cells.
 *
 * Note that with the exception of the "xxx_node" macros, these are
 * lvalues and can be assigned to.
 *
 * NB: There is an unfortunate legacy from a previous incarnation of
 * the MyList API: the macro lfirst() was used to mean "the data in this
 * cons cell". To avoid changing every usage of lfirst(), that meaning
 * has been kept. As a result, lfirst() takes a MyListCell and returns
 * the data it contains; to get the data in the first cell of a
 * MyList, use linitial(). Worse, lsecond() is more closely related to
 * linitial() than lfirst(): given a MyList, lsecond() returns the data
 * in the second list cell.
 */
#define my_lfirst(lc)				((lc)->ptr_value)

#define my_llast(l)				my_lfirst(my_list_last_cell(l))

#define my_list_make_ptr_cell(v)   ((MyListCell) {.ptr_value = (v)})

#define my_linitial(l)             my_lfirst(my_list_nth_cell(l, 0))

#define my_list_make1(x1) \
	my_list_make1_impl(T_List, my_list_make_ptr_cell(x1))

/*
 * Locate the n'th cell (counting from 0) of the list.
 * It is an assertion failure if there is no such cell.
 */
static inline MyListCell *
my_list_nth_cell(const MyList *list, int n)
{
    Assert(list != MYNIL);
    Assert(n >= 0 && n < list->length);
    return &list->elements[n];
}


/*
 * Return the last cell in a non-NIL List.
 */
static inline MyListCell *
my_list_last_cell(const MyList *list)
{
    Assert(list != MYNIL);
    return &list->elements[list->length - 1];
}

/*
 * foreach -
 *	  a convenience macro for looping through a list
 *
 * "cell" must be the name of a "MyListCell *" variable; it's made to point
 * to each MyList element in turn.  "cell" will be NULL after normal exit from
 * the loop, but an early "break" will leave it pointing at the current
 * MyList element.
 *
 * Beware of changing the MyList object while the loop is iterating.
 * The current semantics are that we examine successive list indices in
 * each iteration, so that insertion or deletion of list elements could
 * cause elements to be re-visited or skipped unexpectedly.  Previous
 * implementations of foreach() behaved differently.  However, it's safe
 * to append elements to the MyList (or in general, insert them after the
 * current element); such new elements are guaranteed to be visited.
 * Also, the current element of the MyList can be deleted, if you use
 * foreach_delete_current() to do so.  BUT: either of these actions will
 * invalidate the "cell" pointer for the remainder of the current iteration.
 */
#define my_foreach(cell, lst)	\
	for (MyForEachState cell##__state = {(lst), 0}; \
		 (cell##__state.l != MYNIL && \
		  cell##__state.i < cell##__state.l->length) ? \
		 (cell = &cell##__state.l->elements[cell##__state.i], true) : \
		 (cell = NULL, false); \
		 cell##__state.i++)

/* Functions in src/backend/nodes/list.c */

extern MyList *my_list_make1_impl(NodeTag t, MyListCell datum1);

extern MyList *my_lappend(MyList *list, void *datum);

extern MyList *my_list_delete_last(MyList *list);

extern MyList *my_list_copy(const MyList *oldlist);

typedef int (*my_list_sort_comparator) (const MyListCell *a, const MyListCell *b);

extern void my_list_sort(MyList *list, my_list_sort_comparator cmp);

#endif							/* PG_LIST_H */
